package class_0915skiplist;

//Object:SkipList
/*
 * 跳跃表
 * 二分搜索链表
 */

///Skip lists are a simple randomized structure you'll never forget.
/// it doesn't rotate!
/// ///realize a sorted LinkedList
//    ///
//    /// how to speed up search?
//    /// add a new subWay.
public class SkipList<V> {

    private static final int MAX_LEVEL = 16;//跳表允许的最大层数
    private static final double PROBABILITY = 0.5; // 定义概率常量
    private final Node<V> dummyHead = new Node<V>(Integer.MIN_VALUE, null, MAX_LEVEL);
    private final Node<V> dummyTail = new Node<V>(Integer.MAX_VALUE, null, 0);
    private int curLevel;

    //等级节点的定义。
    public static class Node<V> {
        int key; //键
        V value; //值
        Node<V>[] forwards; //前向指针数组

        public Node(int key, V value, int level) {
            this.key = key;
            this.value = value;
            this.forwards = (Node<V>[]) new Node[level];//前向指针有多少个，或者该等级节点
        }
    }

    {
        for (int i = 0; i < MAX_LEVEL; i++) {
            dummyHead.forwards[i] = dummyTail;
        }
    }

    public SkipList() {
        curLevel = 1;//当前层数。
    }

    public Node<V> search(int key) {
        Node<V> cur = dummyHead; // 从头节点开始遍历

        // 从最高层开始逐层向下遍历---尽可能靠近，越近越好。
        for (int i = curLevel - 1; i >= 0; i--) {
            while (cur.forwards[i] != dummyTail && cur.forwards[i].key < key) {
                cur = cur.forwards[i]; // 在当前层前进---尽可能往右走
            }
        }

        // 回到第0层（原始层），找到目标节点
        cur = cur.forwards[0];

        // 如果目标节点存在且与目标key匹配，则返回该节点
        if (cur != dummyTail && cur.key == key) {
            return cur;
        } else {
            // 如果结果是哨兵节点dummyTail，或者cur.key != key，键为key的节点不存在。
            return null;
        }
    }

    private int randomLevel() {
        int level = 1;//基础层，每个等级节点都应该保证其至少有一层存储原始链表
        while (Math.random() < PROBABILITY && level < MAX_LEVEL) {
            //随机的生成更高层数
            level++;
        }
        return level;//返回
    }

    public void insert(int key, V value) {
        Node<V>[] update = new Node[curLevel];
        Node<V> cur = dummyHead;

        //依旧从最高层出发， 不过这里还要额外记录每层key关键字节点的前驱等级节点。
        for (int i = curLevel - 1; i >= 0; i--) {
            while (cur.forwards[i] != dummyTail && cur.forwards[i].key < key) {
                cur = cur.forwards[i];
            }
            update[i] = cur;  // 记录该层当前节点的位置
        }
        //cur是第一层key关键字节点理论位置的的前驱节点
        //现在往后讨论
        cur = cur.forwards[0];
        if (cur != dummyTail && cur.key == key) {
            cur.value = value;
            return;
        }
        // 如果key不存在，进行插入操作
        // 生成新节点的随机层数
        int level = randomLevel();
        //创建新节点
        Node<V> newNode = new Node<>(key, value, level);

        // 插入新节点，更新每层的前驱指针
        for (int i = 0; i < curLevel; i++) {
            newNode.forwards[i] = update[i].forwards[i];
            update[i].forwards[i] = newNode;
        }
        if (curLevel - level < 0) {
            for (int i = 0; i < level - curLevel; i++) {
                dummyHead.forwards[i + curLevel] = newNode;
                newNode.forwards[i + curLevel] = dummyTail;
            }
        }
        curLevel = level;
    }

    public void delete(int key) {
        Node<V> cur = dummyHead;
        Node<V>[] update = (Node<V>[]) new Node[curLevel];
        for (int i = curLevel - 1; i >= 0; i--) {
            while (cur.forwards[i] != dummyTail && cur.forwards[i].key < key) {
                cur = cur.forwards[i];
            }
            update[i] = cur;
        }
        cur = cur.forwards[0];
        if (cur != dummyTail && cur.key == key) {
            //节点存在
            for (int i = curLevel - 1; i >= 0; i--) {
                if (update[i] == dummyHead && cur.forwards[i] == dummyTail) {
                    dummyHead.forwards[i] = dummyTail;
                    curLevel--;
                } else {
                    //update[i]!=dummyHead || cur.forwards[i]!=dummyTail
                    update[i].forwards[i] = cur.forwards[i];
                }
            }
        }
        //节点不存在，那就啥也不干。
    }

    // 代码废弃部分---食之无味弃之可惜

//    private static final int DEFAULT_MIN_KEY = Integer.MIN_VALUE;
//    private static final Object DEFAULT_VAL = null;
//    private int skipListHighestLevel;//跳表层数
//    private final double p = 0.5;//生成下一层的概率。
//    public SkipListNode<V> head ; //头指针
//    public SkipListNode<V> tail; //尾指针
//    public SkipList(){
//        //头指针指向哨兵位--dummy
//        head = new SkipListNode<>(DEFAULT_MIN_KEY, (V)DEFAULT_VAL);
//        tail = head;
//        skipListHighestLevel = 0;
//    }
//    public void insert(int key, V val){
//    }
//
//    public void insert(SkipListNode<V> node){
//        //设自然的第一层是第0层即原始层。
//        if(head==tail){
//            node.prev = head;
//            head.next = node;
//            tail = node;
//        }else{
//            SkipListNode<V> cur = head.next;
//            while(cur!=null && cur.key>node.key){
//                cur = cur.next;
//            }
//            if(cur==null){
//                tail.next = node;
//                node.prev = tail;
//                tail = node;
//            }
//            else if(cur.key==node.key){
//                //key已经存在了， 只是更新值即可。
//                cur.val = node.val;
//                return ;//更新完，直接返回即可。
//            }
//            else{
//                //中间插入-cur.key>node.key
//                SkipListNode<V> curPre = cur.prev;
//                curPre.next = node;
//                node.prev = curPre;
//                node.next = cur;
//                curPre.prev = node;
//            }
//        }
//        node.forward.add(node);
//        //开始往上堆层数
//        int randLevel = RandLevel();//生成最大的层数。
//        //需要更新哨兵位的层数吗？
//        int curLevel = skipListHighestLevel;
//        for (int i = curLevel; i <= randLevel ; i++) {
//            head.forward.add(head);
//        }
//        for (int i = 0; i < randLevel; i++) {
//            node.forward.add(node);//依次从[1...randLevel]下标处填层。
//        }
//    }
//    /*  获取跳表当前的最高层数*/
//    public int getLevel() {
//        return skipListHighestLevel;
//    }
//
//    public static class SkipListNode<V> {
//        private final int key;
//        private V val;
//        private SkipListNode<V> next;
//        private SkipListNode<V> prev;
//        private ArrayList<SkipListNode<V>> forward;
//        public SkipListNode(int key, V val) {
//            this.key = key;
//            this.val = val;
//            forward = new ArrayList<SkipListNode<V>>();
//        }
//    }
//    public static class SortedList<V>{
//        public static class Node<V>{
//            Node<V> prev,next;
//            int key;
//            V val;
//            public Node(int key, V val) {
//                this.key = key;
//                this.val = val;
//                prev = next = this;
//            }
//        }
//        private Node<V> dummy;//头节点
//        private static final int DEFAULT_SORTEDLIST_MIN_KEY = Integer.MIN_VALUE;
//        private static final Object DEFAULT_SORTEDLIST_VAL= null;
//        public SortedList() {
//            dummy = new Node<>(DEFAULT_SORTEDLIST_MIN_KEY,(V)DEFAULT_SORTEDLIST_VAL);
//        }
//        public boolean add(int key, V val) {
//            return add(new Node<>(key, val));
//        }
//        public boolean add(Node<V> node){
//            Node<V> tail = dummy.prev;//获取最后一个节点
//            tail.next = node;
//            node.prev = tail;
//            node.next = dummy;
//            dummy.prev = node;
//            return true;
//        }
//        public void addLast(int key, V val){
//            add(key, val);
//        }
//        public void addLast(Node<V> node) {
//            add(node);
//        }
//        public void addFirst(int key, V val){
//            addFirst(new Node<>(key, val));
//        }
//        public void addFirst(Node<V> node){
//            node.next = dummy.next;
//            dummy.next.prev = node;
//            dummy.next = node;
//            node.prev = dummy;
//        }
//    }
}
